1. Field of the Invention
The present invention generally relates to compilers for generating application-specific integrated circuits and, more particularly, to compilers for generating conditional-sum carry structures for use in application-specific integrated circuits.
2. State of the Art
It is well known to provide integrated circuits, or "chips", of the type known as application-specific integrated circuits (ASICs). In essence, ASIC chips are custom-designed circuits of the LSI (large scale integration) or VLSI (very large scale integration) class. ASIC chips often include one or more functional blocks or "cells" which, individually, may be classified as LSI or VLSI circuits. For instance, the cells within an ASIC chip may comprise one or more random access memories (RAMs), read-only memories (ROMs), or arithmetic logic units (ALUs). Also, cells can be as simple as an individual logic gate.
To efficiently and economically design ASIC chips, it is necessary to use automated systems, usually referred to as compilers. Compilers allow circuit designers to custom design ASIC chips by drawing upon libraries containing standardized designs of circuits that can comprise cells within ASIC chips. Also, compilers can themselves include compiling sub-systems. For example, in designing an ASIC chip with a compiler, a design engineer may want a functional block to include one or more ALU circuits and, rather than designing the ALU circuits himself, the engineer may want a compiling sub-system to design the ALU circuits while including some special connections that he has specified.
Compilers can, of course, generate circuits for uses other than in ASIC chips. For instance, compiler systems can design circuits for implementation on printed circuit boards. The following emphasis on compilers that generate ASIC chips is not intended to exclude their other uses.
In view of the preceding discussion, it can be appreciated that, for compiler systems to be practical and commercially acceptable, the systems must allow circuit designers flexibility in modifying functional blocks within ASIC chips. For instance, circuit designers often want the flexibility to modify standard ALU cells to accommodate different bit widths. For such modifications to be easily accomplished by automated compilers (or compiling sub-systems), the standard cells must have regular and relatively non-complex architectures. At the same time, however, the standard cells usually must be able to process data quickly, so that their host circuits are not slowed. In particular, it is usually important that ALU cells operate at high speeds.
To provide high-speed ALU circuits, it is known to implement the circuits as so-called "conditional-sum adders". The advantage of conditional-sum adders is that their data delay is a logarithmic function of bit width. Thus, a 32-bit ALU circuit which is implemented as a conditional-sum adder has only a slightly longer delay than a 16-bit conditional-sum adder (since the logarithm of the number 32 only slightly exceeds the logarithm of the number 16). By way of contrast, conventional adders have data delays that increase approximately linearly with bit width; for example, a conventional 32-bit ripple-carry adder is typically only about one-half as fast as a 16-bit ripple-carry adder. In fact, the slowness of ripple-carry adders can be substantial constraint on circuit designs at bit widths greater than about sixteen bits.
The speed of operation of conditional-sum adders is primarily a result of their generating sets of two different carry-out bits at each of a number of internal stages. More particularly, at various internal stages, conditional-sum adders generate a first carry-out bit based upon the assumption that the actual carry-in bit to the stage will have one binary value (e.g., high or binary 1) and, also, generate a second carry-out bit based upon the assumption that the actual carry-in bit will have a complementary binary value (e.g. low or binary 0). The first and second carry-out bits are usually referred to as either "provisional" or "conditional" carry bits, and the two terms will be used interchangeably herein.
Because provisional sums and provisional carry-out bits can be calculated at various stages of a conditional-sum adder without the stages waiting for actual carry-in bits, numerous provisional additions can be made at the same time. Thereafter, the actual carry bits can "ripple" through a conditional-sum adder at a rate which is faster than with ordinary adders, especially, ripple-carry adders of high bit widths.
Although conditional-sum adders provide benefits in terms of data-handling speed at high bit widths, the fact that provisional carry-out bits are generated at numerous stages in the adders results in the devices being "architecturally" complex and irregular. Moreover, the architecture of those devices causes modifications, such as bit-width modifications, to be difficult to accomplish. Thus, conditional-sum adders of conventional architecture cannot be readily generated by computer algorithms and, therefore, are not well suited for use by automated compiling systems.
Conditional-sum adders are further described at chapter 4 of the text, Computer Arithmetic Principles, Architecture, and Design, by Kai Hwang (Wiley, 1979). As explained in that text, conditional-sum adders can be grouped to accomplish operations such as multiplication and division. Furthermore, by employing additional logic elements, the adders can be transformed into ALU circuits that perform various binary logic operations as well as arithmetic operations. Accordingly, the emphasis in the following on conditional-sum adders is not intended to exclude their use as ALU circuits.